package com.heima.algorithm.greedy;

import cn.hutool.core.bean.BeanUtil;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 分数背包问题
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/3 12:48
 */
public class FractionalKnapsackProblem {
    /*
     问题描述：

     编号   重量（升）   总价值    名称
      0         4       24        水
      1         8       160       牛奶
      2         2       4000      五粮液
      3         6       108       可乐
      4         1       4000      茅台

     选取10升最贵的液体，每种液体可以全部选也可以选部分
     */

    /**
     * 物品类
     */
    public static class Item{
        int index;
        String name;
        double weight;
        double value;

        public Item() {
        }

        public Item(int index, String name, double weight, double value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        public double valuePerWeight() {
            return value / weight;
        }

        public String name() {
            return name;
        }

        public double value() {
            return value;
        }

        @Override
        public String toString() {
            return "{" +
                    "name='" + name + '\'' +
                    ", weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }

    /**
     * 选择最大价值
     * @param itemList 物品列表
     * @param totalWeight 总重量
     * @return  选择结果
     */
    public static List<Item> select(List<Item> itemList, double totalWeight) {
        // itemList.sort((item1, item2) -> Double.compare(item2.valuePerWeight(), item1.valuePerWeight()));
        itemList.sort(Comparator.comparingDouble(Item::valuePerWeight).reversed());

        List<Item> result = new ArrayList<>();
        for (Item item : itemList) {
            if (item.weight <= totalWeight){
                result.add(item);
                totalWeight -= item.weight;
            }else {
                Item added = new Item();
                added.index = item.index;
                added.name = item.name;

                added.weight = totalWeight;
                added.value = totalWeight * item.valuePerWeight();
                result.add(added);
                break;
            }
        }
        return result;
    }
}
